洛谷 3831 [SHOI2012]回家的路 题解

发表于 | 阅读次数：
本文字数： 1k 字 | 阅读时长 ≈ 5 分钟

题意简述

$n$ 行 $n$ 列的矩阵上，只有 $m$ 个“关键点”处（在第 $x$ 行 $y$ 列）才能拐弯。从格子到上下左右四个相邻格子花费 $2$，转弯花费 $1$。 求从某个位置走到另一个位置的最小花费。无解输出 $-1​$。

思路

新建两个点 $S$ 和 $T$ 表示起点。 然后把所有点 $A$（包括关键点和 $S,T$） 拆成两个点 $A_1$ 和 $A_2$，分别表示横向跑和纵向跑。

对于所有关键点 $K$ （不包括 $S,T$），$K_1$ 到 $K_2$ 连一条边权为 $1$ 的无向边，表示换乘。

然后对于所有同一行 （$x$ 相同）的点，按照列号 $y$ 排序。对于相邻的 $A,B$，连边 $(A_1,B_1,2\times dis)$，其中 $dis$ 为 $A,B$ 两点 $y$ 值的距离。为啥乘二，是因为相邻格子要花费 $2$。 同一列同理（同一列连的是 $A_2$ 和 $B_2$）。

然后我们从 $S_1$ 跑到 $T_1,T_2$，从 $S_2$ 跑到 $T_1,T_2$ ，四种方案，看哪个最小。如果都不能到达…那就输出 $-1$。

代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 255555
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	int I()
	{
	    int x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    return (x=(f==1)?x:-x);
	}
	void Rd(int cnt,...)
	{
	    va_list args; va_start(args,cnt);
	    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
	    va_end(args);
	}
	class Graph
	{
	    public:
	        int head[N];
	        int EdgeCount;
	        struct Edge
	        {
	            int To,Label,Next;
	        }Ed[1666666];
	        void clear(int _V=N,int _E=N<<1) 
	        {
	            memset(Ed,-1,sizeof(Edge)*(_E));
	            memset(head,-1,sizeof(int)*(_V));
	            EdgeCount=-1;
	        }
	        void AddEdge(int u,int v,int w=1)
	        {
	            Ed[++EdgeCount]=(Edge){v,w,head[u]};
	            head[u]=EdgeCount;
	        }
	        void Add2(int u,int v,int w=1) 
	        {
	        	// printf("Add %d %d\n",u,v);
	        	AddEdge(u,v,w);AddEdge(v,u,w);
	        }
	        int Start(int u) {return head[u];}
	        int To(int u){return Ed[u].To;}
	        int Label(int u){return Ed[u].Label;}
	        int Next(int u){return Ed[u].Next;}
	}G;
	struct node{int x,y,id;}a[N]; 
	bool cmp_x(node a,node b) {return a.x<b.x or (a.x==b.x and a.y<b.y);}
	bool cmp_y(node a,node b) {return a.y<b.y or (a.y==b.y and a.x<b.x);}
	#define lin(x) x
	#define col(x) (x)+m+2

	int n,m;
	void Input()
	{
		Rd(2,&n,&m); F(i,1,m) a[i]=(node){I(),I(),i};
		a[m+1]=(node){I(),I(),m+1};
		a[m+2]=(node){I(),I(),m+2};
	}

	void Build()
	{
		G.clear();
		sort(a+1,a+m+3,cmp_x);
		F(i,2,m+2) if (a[i].x==a[i-1].x) G.Add2(lin(a[i].id),lin(a[i-1].id),2*abs(a[i].y-a[i-1].y));
		sort(a+1,a+m+3,cmp_y);
		F(i,2,m+2) if (a[i].y==a[i-1].y) G.Add2(col(a[i].id),col(a[i-1].id),2*abs(a[i].x-a[i-1].x));
		F(i,1,m+2) if (a[i].id<=m) G.Add2(lin(a[i].id),col(a[i].id),1); 
	}
	struct djnode{int v,w;}; bool operator<(djnode a,djnode b){return a.w>b.w;}
	priority_queue<djnode> Q; bool vis[N];int dis[N];
	void Dijkstra(int s)
	{
		MEM(dis,0x3f); FK(vis); while(!Q.empty()) Q.pop();
		Q.push((djnode){s,0}); dis[s]=0;
		while(!Q.empty())
		{
			djnode Min=Q.top(); Q.pop();
			int u=Min.v;	
			if (vis[u]) continue;
			vis[u]=1;

			Tra(i,u) if (!vis[v] and dis[v]>dis[u]+G.Label(i)) 
			{
				dis[v]=dis[u]+G.Label(i);
				Q.push((djnode){v,dis[v]});
			}
		}
		// F(i,1,2*(m+2)) printf("%d ",dis[i]>1e9?-1:dis[i]);
		// putchar('\n'); 
	}
	void Soviet()
	{
		Build();
		int ans=0x3f3f3f3f;
		Dijkstra(lin(m+1)); ans=min(ans,min(dis[lin(m+2)],dis[col(m+2)]));
		Dijkstra(col(m+1)); ans=min(ans,min(dis[lin(m+2)],dis[col(m+2)]));
		printf("%d\n",ans>1e9?-1:ans);
	}

	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w